package com.example.algorithm.sort.insert;

/**
 * @program: algorithm
 * @description: 插入排序
 * @packagename: com.example.algorithm.sort.insert
 * @author: Jay
 * @date: 2022/03/24 16:55:03
 **/
public class Insertion {

    /**
     * 最坏
     * 比较次数：n-1,n-2...1:n^2/2-n/2
     * 交换次数 n-1,n-2...1:n^2/2-n/2
     * O(N^2)
     * @param a
     */
    public static void sort(Comparable[] a){
        for (int i = 1; i < a.length; i++) {

            for (int j = i; j > 0; j--){
                //比较j处的值和j-1处的值，如果j-1处的值比索引j处的值大则交换，否则交换
                if (greater(a[j-1],a[j])){
                    exch(a,j,j-1);
                }
            }
        }
    }

    /**
     * 比较a>b
     */
    public static boolean greater(Comparable a, Comparable b){
        return a.compareTo(b)>0;
    }

    /**
     * 数组元素i，j交换位置
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
